//给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 
//
// 示例: 
//
// 输入: [1,2,3,null,5,null,4]
//输出: [1, 3, 4]
//解释:
//
//   1            <---
// /   \
//2     3         <---
// \     \
//  5     4       <---
// 
// Related Topics 树 深度优先搜索 广度优先搜索 
// 👍 288 👎 0

package leetcode.editor.cn;

import leetcode.editor.commons.TreeNode;
import sun.reflect.generics.tree.Tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

//Java：二叉树的右视图
public class P199BinaryTreeRightSideView{
    public static void main(String[] args) {
        Solution solution = new P199BinaryTreeRightSideView().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    /*
    * 使用广度优先搜索进行层次遍历，并将最右边
    * 每个节点都被出队和入队一次，时间复杂度为O(n)
    * 创建了一个队列，空间复杂度也为O(n)
    * */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        if(root==null){
            return res;
        }
        Queue<TreeNode> queue=new ArrayDeque<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int n=queue.size();
            for(int i=0;i<n;i++){
                TreeNode node=queue.poll();
                if (node.left!=null){
                    queue.offer(node.left);
                }

                if(node.right!=null){
                    queue.offer(node.right);
                }

                if(i==n-1){
                    res.add(node.val);
                }
            }
        }

        return res;
    }

    /*
    * 使用深度优先搜索解决这个问题
    *
    * */
    public List<Integer> rightSideView1(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        dfs(root,0,res);

        return res;
    }
    /*
    * 按照根右左的顺序进行访问。  、
    * 每次最右边一个节点优先被访问。
    *
    * 时间复杂度分析
    * 因为每个节点都被访问了一次，所以时间复杂度为O(n)
    * 因为不是一颗平衡的二叉树，二叉树的深度至少为logn,可能会退化为一个链表，因此所用的栈空间也为O(n)
    * */
    public void dfs(TreeNode root,int depth,List<Integer> res){
        if(root==null){
            return;
        }
        if(depth==res.size()){//是该层的最后一个节点,也是该层第一个被访问的节点
            res.add(root.val);
        }
        depth++;
        dfs(root.right,depth,res);
        dfs(root.left,depth,res);
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
